package sort;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 快速排序 O(nlogn)
 */
public class QuickSort {

    /** 递归 **/
    public static void quickSort(int[] arr) {
        quickSortInternal(arr, 0, arr.length - 1);
    }
    //在区间[l, r]内进行快速排序
    private static void quickSortInternal(int[] arr, int l, int r) {
        //边界条件：只剩下一个元素时
        if(l >= r){
            return;
        }
//        /** 优化 **/
//        if(r - l <= 15){
//            //小区间内直接使用插入排序
//            insertionSort(arr, l, r);
//            return;
//        }
        // 先获取分区点
        // 所谓分区点的元素会在分区排序函数后，落在最终位置
        // 最终位置：左边都是<它的元素，右边都是>=它的元素
        int p = partition(arr, l, r);
        //将分区点两边的区间进行排序
        quickSortInternal(arr, l, p -1);
        quickSortInternal(arr, p + 1, r);
    }
    private static ThreadLocalRandom random = ThreadLocalRandom.current();

    /**
     * 区间[l, r]的随机分区函数
     * @param arr
     * @param l
     * @param r
     * @return 返回分区点的索引
     */
    private static int partition(int[] arr, int l, int r) {
        //随机选择一个元素作为基准值
        int randomIndex = random.nextInt(l, r);
        //把基准元素放到第一位
        swap(arr, l, randomIndex);
        int v = arr[l];
        //l  [l + 1, j]  [j + 1, i - 1]   i
        //v     <v            >=v       正在扫描的元素
        int j = l;
        for(int i = l + 1; i <= r; i++){
            if(arr[i] < v){
                swap(arr, j + 1, i);
                j ++;
            }
        }
        //交换基准元素和最后一个<v的元素的位置
        swap(arr, l, j);
        //返回分区点的坐标
        return j;
    }
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] + arr[j] - (arr[j] = arr[i]);
    }
    //插入排序法: 区间内[l, r]
    private static void insertionSort(int[] arr, int l, int r) {
        // i表示无序区间的首元素
        for(int i = l + 1; i <= r; i++){
            for(int j = i; j - 1 >= l && arr[j] < arr[j-1]; j--){
                arr[j] = arr[j] + arr[j-1] - (arr[j-1] = arr[j]);
            }
        }
    }

    /** 借助栈实现非递归分治 **/
    public static void quickSortNonRecursion(int[] arr) {
        //创建栈
        Deque<Integer> stack = new ArrayDeque<>();
        //存放整个数组的起始索引和终了索引
        int l = 0, r = arr.length - 1;
        stack.push(l);
        stack.push(r);
        //栈不为空，说明子区间还没有处理完
        while(!stack.isEmpty()){
            //弹出当前需要处理的子区间的左右边界
            int right = stack.pop();
            int left = stack.pop();
            //判断子区间长度
            if(left >= right){
                //说明子区间中只有一个元素
                continue;
            }
            //找到基准值
            int p = partition(arr, left, right);
            //利用栈存储左区间的边界，以便下一层循环时处理
            stack.push(left);
            stack.push(p - 1);
            //利用栈存储右区间的边界
            stack.push(p + 1);
            stack.push(right);
        }
    }

    /** 递归：二路快排 **/
    public static void quickSort2(int[] arr) {
        quickSortInternal2(arr, 0, arr.length - 1);
    }
    //在区间[l, r]内进行快速排序
    private static void quickSortInternal2(int[] arr, int l, int r) {
        //边界条件：只剩下一个元素时
        if(l >= r){
            return;
        }
        //优化：if(r - l <= 15) { insertionSort(arr, l, r); return; }
        int p = partition2(arr, l, r);
        //将分区点两边的区间进行排序
        quickSortInternal2(arr, l, p -1);
        quickSortInternal2(arr, p + 1, r);
    }
    /**
     * 区间[l, r]的二路分区函数
     * @param arr
     * @param l
     * @param r
     * @return 返回分区点的索引
     */
    private static int partition2(int[] arr, int l, int r) {
        //选取随机基准值
        int randomIndex = random.nextInt(l, r);
        swap(arr, randomIndex, l);
        // l [l + 1, i - 1]  i    j  [j + 1, r]
        // v     <=v      正在扫描的元素    >=v
        int v = arr[l], i = l + 1, j = r;
        //当i > j时，扫描结束
        while(i <= j){
            //if语句的分支：要么交换，要么让它俩都走到符合交换条件的位置
            if(arr[i] >= v && arr[j] <= v){
                swap(arr, i, j);
                i ++;
                j --;
            }else{
                if(arr[i] < v){
                    i ++;
                }
                if(arr[j] > v){
                    j --;
                }
            }
        }
        //此时,最后一个<=V的元素索引在i - 1处
        swap(arr, l, i - 1);
        return i - 1;
    }

    /** 递归：三路快排 **/
    public static void quickSort3(int[] arr) {
        quickSortInternal3(arr, 0, arr.length - 1);
    }
    //在区间[l, r]内进行快速排序
    private static void quickSortInternal3(int[] arr, int l, int r) {
        //边界条件：只剩下一个元素时
        if(l >= r){
            return;
        }
        //优化：if(r - l <= 15) { insertionSort(arr, l, r); return; }
        int[] p = partition3(arr, l, r);
        //将分区点两边的区间进行排序
        quickSortInternal3(arr, l, p[0] -1);
        quickSortInternal3(arr, p[1] + 1, r);
    }
    /**
     * 区间[l, r]的三路分区函数
     * @param arr
     * @param l
     * @param r
     * @return 返回分区点的索引
     */
    private static int[] partition3(int[] arr, int l, int r) {
        //选取随机基准值
        int randomIndex = random.nextInt(l, r);
        swap(arr, randomIndex, l);
        // l [l + 1, lt]  [lt + 1, i)    i     [gt, r]
        // v      <v           =v   正在扫描的元素   >v
        int v = arr[l], lt = l, i = lt + 1, gt = r + 1;
        //当i >= gt时，扫描结束
        while(i < gt){
            if(arr[i] < v){
                swap(arr, i, lt + 1);
                lt ++;
                i ++;
            }else if(arr[i] == v){
                i ++;
            }else{
                // arr[i] > v
                swap(arr, i, gt - 1);
                gt --;
            }
        }
        //此时,[lt + 1, gt - 1]区间内的元素=V
        swap(arr, l, lt);
        int[] p = {lt, gt - 1};
        return p;
    }
}
